#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2020/6/6 11:45
# @USER    : Shengji He
# @File    : LongestConsecutiveSequence.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:
from typing import List


class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        """
        Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

        Your algorithm should run in O(n) complexity.

        Example:
            Input: [100, 4, 200, 1, 3, 2]

            Output: 4

            Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

        :param nums: List[int]
        :return: int
        """
        nums = list(set(nums))
        if len(nums) < 2:
            return len(nums)
        nums.sort()
        longest = 1
        current = 1
        for i in range(1, len(nums)):
            if nums[i] - nums[i - 1] == 1:
                current += 1
            else:
                current = 1
            longest = max(longest, current)

        return max(longest, current)
        # nums = list(set(nums))
        # if len(nums) < 2:
        #     return len(nums)
        # heapq.heapify(nums)
        # ans = 1
        # flag = 1
        # val_past = heapq.heappop(nums)
        # while nums:
        #     val = heapq.heappop(nums)
        #     if val - val_past == 1:
        #         flag += 1
        #     elif val == val_past:
        #         continue
        #     else:
        #         flag = 1
        #     ans = [flag, ans][ans>flag]
        #     val_past = val
        # return ans


if __name__ == '__main__':
    S = Solution()
    # nums = [2, 6, 5]
    nums = [1, 2, 0, 1]
    # nums = [100, 4, 200, 1, 3, 2]
    print(S.longestConsecutive(nums))
    print('done')
